home *** CD-ROM | disk | FTP | other *** search
/ NOVA - For the NeXT Workstation / NOVA - For the NeXT Workstation.iso / Apps / ArchiveUtils / nx_arc / arcsqs.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-20  |  11.0 KB  |  446 lines
  1. /*  ARC - Archive utility - SQUASH
  2.  
  3. (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
  4.  
  5.  This is a quick hack to ARCLZW to make it handle squashed archives.
  6.  Dan Lanciani (ddl@harvard.*) July 87
  7.  
  8. */
  9. #include <stdio.h>
  10. #include "arc.h"
  11.  
  12. /* definitions for the new dynamic Lempel-Zev crunching */
  13.  
  14. #define BITS   13        /* maximum bits per code */
  15. #define HSIZE  10007        /* 80% occupancy */
  16. #define INIT_BITS 9        /* initial number of bits/code */
  17. static INT      n_bits;        /* number of bits/code */
  18. static INT      maxcode;    /* maximum code, given n_bits */
  19. #define MAXCODE(n)      ((1<<(n)) - 1)    /* maximum code calculation */
  20. static INT      maxcodemax = 1 << BITS;    /* largest possible code (+1) */
  21.  
  22. static unsigned char buf[BITS];    /* input/output buffer */
  23.  
  24. static unsigned char lmask[9] =    /* left side masks */
  25. {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  26. static unsigned char rmask[9] =    /* right side masks */
  27. {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  28.  
  29. static INT      offset;        /* byte offset for code output */
  30. static long     in_count;    /* length of input */
  31. static long     bytes_out;    /* length of compressed output */
  32. static unsigned INT ent;
  33.  
  34. static long     htab[HSIZE];    /* hash code table   (crunch) */
  35. static unsigned INT codetab[HSIZE];    /* string code table (crunch) */
  36.  
  37. static unsigned INT *prefix = codetab;    /* prefix code table (uncrunch) */
  38.  
  39. static unsigned char suffix[HSIZE];    /* suffix table (uncrunch) */
  40. static INT      free_ent;    /* first unused entry */
  41. static INT      firstcmp;    /* true at start of compression */
  42. static unsigned char stack[HSIZE];    /* local push/pop stack */
  43.  
  44. /*
  45.  * block compression parameters -- after all codes are used up,
  46.  * and compression rate changes, start over.
  47.  */
  48.  
  49. static INT      clear_flg;
  50. static long     ratio;
  51. #define CHECK_GAP 10000        /* ratio check interval */
  52. static long     checkpoint;
  53. static INT    putcode();
  54.  
  55. /*
  56.  * the next two codes should not be changed lightly, as they must not
  57.  * lie within the contiguous general code space.
  58.  */
  59. #define FIRST   257        /* first free entry */
  60. #define CLEAR   256        /* table clear output code */
  61.  
  62. static INT 
  63. cl_block(t)            /* table clear for block compress */
  64.     FILE           *t;    /* our output file */
  65. {
  66.     long            rat;
  67.  
  68.     checkpoint = in_count + CHECK_GAP;
  69.  
  70.     if (in_count > 0x007fffff) {    /* shift will overflow */
  71.         rat = bytes_out >> 8;
  72.         if (rat == 0)    /* Don't divide by zero */
  73.             rat = 0x7fffffff;
  74.         else
  75.             rat = in_count / rat;
  76.     } else
  77.         rat = (in_count << 8) / bytes_out;    /* 8 fractional bits */
  78.  
  79.     if (rat > ratio)
  80.         ratio = rat;
  81.     else {
  82.         ratio = 0;
  83.         setmem(htab, HSIZE * sizeof(long), 0xff);
  84.         free_ent = FIRST;
  85.         clear_flg = 1;
  86.         putcode(CLEAR, t);
  87.     }
  88. }
  89.  
  90. /*****************************************************************
  91.  *
  92.  * Output a given code.
  93.  * Inputs:
  94.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  95.  *              that n_bits =< (long)wordsize - 1.
  96.  * Outputs:
  97.  *      Outputs code to the file.
  98.  * Assumptions:
  99.  *      Chars are 8 bits long.
  100.  * Algorithm:
  101.  *      Maintain a BITS character long buffer (so that 8 codes will
  102.  * fit in it exactly).  When the buffer fills up empty it and start over.
  103.  */
  104.  
  105. static INT 
  106. putcode(code, t)        /* output a code */
  107.     INT             code;    /* code to output */
  108.     FILE           *t;    /* where to put it */
  109. {
  110.     INT             r_off = offset;    /* right offset */
  111.     INT             bits = n_bits;    /* bits to go */
  112.     unsigned char  *bp = buf;    /* buffer pointer */
  113.     INT             n;    /* index */
  114.  
  115.     if (code >= 0) {    /* if a real code *//* Get to the first byte. */
  116.         bp += (r_off >> 3);
  117.         r_off &= 7;
  118.  
  119.         /*
  120.          * Since code is always >= 8 bits, only need to mask the
  121.          * first hunk on the left. 
  122.          */
  123.         *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  124.         bp++;
  125.         bits -= (8 - r_off);
  126.         code >>= (8 - r_off);
  127.  
  128.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  129.         if (bits >= 8) {
  130.             *bp++ = code;
  131.             code >>= 8;
  132.             bits -= 8;
  133.         }
  134.         /* Last bits. */
  135.         if (bits)
  136.             *bp = code;
  137.  
  138.         offset += n_bits;
  139.  
  140.         if (offset == (n_bits << 3)) {
  141.             bp = buf;
  142.             bits = n_bits;
  143.             bytes_out += bits;
  144.             do
  145.                 putc_pak(*bp++, t);
  146.             while (--bits);
  147.             offset = 0;
  148.         }
  149.         /*
  150.          * If the next entry is going to be too big for the code
  151.          * size, then increase it, if possible. 
  152.          */
  153.         if (free_ent > maxcode || clear_flg > 0) {    /* Write the whole
  154.                                  * buffer, because the
  155.                                  * input side won't
  156.                                  * discover the size
  157.                                  * increase until after
  158.                                  * it has read it. */
  159.             if (offset > 0) {
  160.                 bp = buf;    /* reset pointer for writing */
  161.                 bytes_out += n = n_bits;
  162.                 while (n--)
  163.                     putc_pak(*bp++, t);
  164.             }
  165.             offset = 0;
  166.  
  167.             if (clear_flg) {    /* reset if clearing */
  168.                 maxcode = MAXCODE(n_bits = INIT_BITS);
  169.                 clear_flg = 0;
  170.             } else {/* else use more bits */
  171.                 n_bits++;
  172.                 if (n_bits == BITS)
  173.                     maxcode = maxcodemax;
  174.                 else
  175.                     maxcode = MAXCODE(n_bits);
  176.             }
  177.         }
  178.     } else {        /* dump the buffer on EOF */
  179.         bytes_out += n = (offset + 7) / 8;
  180.  
  181.         if (offset > 0)
  182.             while (n--)
  183.                 putc_pak(*bp++, t);
  184.         offset = 0;
  185.     }
  186. }
  187.  
  188. /*****************************************************************
  189.  *
  190.  * Read one code from the standard input.  If EOF, return -1.
  191.  * Inputs:
  192.  *      cmpin
  193.  * Outputs:
  194.  *      code or -1 is returned.
  195.  */
  196.  
  197. static INT 
  198. getcode(f)            /* get a code */
  199.     FILE           *f;    /* file to get from */
  200. {
  201.     INT             code;
  202.     static INT      offset = 0, size = 0;
  203.     INT             r_off, bits;
  204.     unsigned char  *bp = buf;
  205.  
  206.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {    /* If the next entry
  207.                                      * will be too big for
  208.                                      * the current code
  209.                                      * size, then we must
  210.                                      * increase the size. 
  211.                                      * This implies reading
  212.                                      * a new buffer full,
  213.                                      * too. */
  214.         if (free_ent > maxcode) {
  215.             n_bits++;
  216.             if (n_bits == BITS)
  217.                 maxcode = maxcodemax;    /* won't get any bigger
  218.                              * now */
  219.             else
  220.                 maxcode = MAXCODE(n_bits);
  221.         }
  222.         if (clear_flg > 0) {
  223.             maxcode = MAXCODE(n_bits = INIT_BITS);
  224.             clear_flg = 0;
  225.         }
  226.         for (size = 0; size < n_bits; size++) {
  227.             if ((code = getc_unp(f)) == EOF)
  228.                 break;
  229.             else
  230.                 buf[size] = code;
  231.         }
  232.         if (size <= 0)
  233.             return -1;    /* end of file */
  234.  
  235.         offset = 0;
  236.         /* Round size down to integral number of codes */
  237.         size = (size << 3) - (n_bits - 1);
  238.     }
  239.     r_off = offset;
  240.     bits = n_bits;
  241.  
  242.     /*
  243.      * Get to the first byte. 
  244.      */
  245.     bp += (r_off >> 3);
  246.     r_off &= 7;
  247.  
  248.     /* Get first part (low order bits) */
  249.     code = (*bp++ >> r_off);
  250.     bits -= 8 - r_off;
  251.     r_off = 8 - r_off;    /* now, offset into code word */
  252.  
  253.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  254.     if (bits >= 8) {
  255.         code |= *bp++ << r_off;
  256.         r_off += 8;
  257.         bits -= 8;
  258.     }
  259.     /* high order bits. */
  260.     code |= (*bp & rmask[bits]) << r_off;
  261.     offset += n_bits;
  262.  
  263.     return code;
  264. }
  265.  
  266. /*
  267.  * compress a file
  268.  *
  269.  * Algorithm:  use open addressing double hashing (no chaining) on the
  270.  * prefix code / next character combination.  We do a variant of Knuth's
  271.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  272.  * secondary probe.  Here, the modular division first probe is gives way
  273.  * to a faster exclusive-or manipulation.  Also do block compression with
  274.  * an adaptive reset, where the code table is cleared when the compression
  275.  * ratio decreases, but after the table fills.  The variable-length output
  276.  * codes are re-sized at this point, and a special CLEAR code is generated
  277.  * for the decompressor.
  278.  */
  279.  
  280. INT 
  281. sqinit_cm(f, t)            /* initialize for compression */
  282.     FILE           *f;    /* file we will be compressing */
  283.     FILE           *t;    /* where we will put it */
  284. {
  285.     offset = 0;
  286.     bytes_out = 0;
  287.     clear_flg = 0;
  288.     ratio = 0;
  289.     in_count = 1;
  290.     checkpoint = CHECK_GAP;
  291.     maxcode = MAXCODE(n_bits = INIT_BITS);
  292.     free_ent = FIRST;
  293.     setmem(htab, HSIZE * sizeof(long), 0xff);
  294.     n_bits = INIT_BITS;    /* set starting code size */
  295.  
  296.     firstcmp = 1;        /* next byte will be first */
  297. }
  298.  
  299. INT 
  300. sqputc_cm(c, t)            /* compress a character */
  301.     unsigned char   c;    /* character to compress */
  302.     FILE           *t;    /* where to put it */
  303. {
  304.     static long     fcode;
  305.     static INT      hshift;
  306.     INT             i;
  307.     INT             disp;
  308.  
  309.     if (firstcmp) {        /* special case for first byte */
  310.         ent = c;    /* remember first byte */
  311.  
  312.         hshift = 0;
  313.         for (fcode = (long) HSIZE; fcode < 65536L; fcode *= 2L)
  314.             hshift++;
  315.         hshift = 8 - hshift;    /* set hash code range bund */
  316.  
  317.         firstcmp = 0;    /* no longer first */
  318.         return;
  319.     }
  320.     in_count++;
  321.     fcode = (long) (((long) c << BITS) + ent);
  322.     i = (c << hshift) ^ ent;/* xor hashing */
  323.  
  324.     if (htab[i] == fcode) {
  325.         ent = codetab[i];
  326.         return;
  327.     } else if (htab[i] < 0)    /* empty slot */
  328.         goto nomatch;
  329.     disp = HSIZE - i;    /* secondary hash (after G.Knott) */
  330.     if (i == 0)
  331.         disp = 1;
  332.  
  333. probe:
  334.     if ((i -= disp) < 0)
  335.         i += HSIZE;
  336.  
  337.     if (htab[i] == fcode) {
  338.         ent = codetab[i];
  339.         return;
  340.     }
  341.     if (htab[i] > 0)
  342.         goto probe;
  343.  
  344. nomatch:
  345.     putcode(ent, t);
  346.     ent = c;
  347.     if (free_ent < maxcodemax) {
  348.         codetab[i] = free_ent++;    /* code -> hashtable */
  349.         htab[i] = fcode;
  350.     } else if ((long) in_count >= checkpoint)
  351.         cl_block(t);
  352. }
  353.  
  354. long 
  355. sqpred_cm(t)            /* finish compressing a file */
  356.     FILE           *t;    /* where to put it */
  357. {
  358.     putcode(ent, t);    /* put out the final code */
  359.     putcode(-1, t);        /* tell output we are done */
  360.  
  361.     return bytes_out;    /* say how big it got */
  362. }
  363.  
  364. /*
  365.  * Decompress a file.  This routine adapts to the codes in the file
  366.  * building the string table on-the-fly; requiring no table to be stored
  367.  * in the compressed file.  The tables used herein are shared with those of
  368.  * the compress() routine.  See the definitions above.
  369.  */
  370.  
  371. INT 
  372. sqdecomp(f, t)            /* decompress a file */
  373.     FILE           *f;    /* file to read codes from */
  374.     FILE           *t;    /* file to write text to */
  375. {
  376.     unsigned char  *stackp;
  377.     INT             finchar;
  378.     INT             code, oldcode, incode;
  379.  
  380.     n_bits = INIT_BITS;    /* set starting code size */
  381.     clear_flg = 0;
  382.  
  383.     /*
  384.      * As above, initialize the first 256 entries in the table. 
  385.      */
  386.     maxcode = MAXCODE(n_bits = INIT_BITS);
  387.     for (code = 255; code >= 0; code--) {
  388.         prefix[code] = 0;
  389.         suffix[code] = (unsigned char) code;
  390.     }
  391.     free_ent = FIRST;
  392.  
  393.     finchar = oldcode = getcode(f);
  394.     if (oldcode == -1)    /* EOF already? */
  395.         return;        /* Get out of here */
  396.     putc_unp((char) finchar, t);    /* first code must be 8 bits=char */
  397.     stackp = stack;
  398.  
  399.     while ((code = getcode(f)) > -1) {
  400.         if (code == CLEAR) {
  401.             for (code = 255; code >= 0; code--)
  402.                 prefix[code] = 0;
  403.             clear_flg = 1;
  404.             free_ent = FIRST - 1;
  405.             if ((code = getcode(f)) == -1)    /* O, untimely death! */
  406.                 break;
  407.         }
  408.         incode = code;
  409.         /*
  410.          * Special case for KwKwK string. 
  411.          */
  412.         if (code >= free_ent) {
  413.             *stackp++ = finchar;
  414.             code = oldcode;
  415.         }
  416.         /*
  417.          * Generate output characters in reverse order 
  418.          */
  419.         while (code >= 256) {
  420.             *stackp++ = suffix[code];
  421.             code = prefix[code];
  422.         }
  423.         *stackp++ = finchar = suffix[code];
  424.  
  425.         /*
  426.          * And put them out in forward order 
  427.          */
  428.         do
  429.             putc_unp(*--stackp, t);
  430.         while (stackp > stack);
  431.  
  432.         /*
  433.          * Generate the new entry. 
  434.          */
  435.         if ((code = free_ent) < maxcodemax) {
  436.             prefix[code] = (unsigned short) oldcode;
  437.             suffix[code] = finchar;
  438.             free_ent = code + 1;
  439.         }
  440.         /*
  441.          * Remember previous code. 
  442.          */
  443.         oldcode = incode;
  444.     }
  445. }
  446.